package cn.dapeng.tree.binary;

import cn.dapeng.utils.BinaryTreeCreator;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树序列化和反序列号
 * <p>
 * 序列号把树存在文件中
 * 反序列化把文件还原成二叉树
 * <p>
 * <p>
 * 二叉树序列化的方式， 本例子中有三种 先序、后序、按层方式序列化
 * 不存在中序方式的序列化，举例:
 * 2                   1
 * /   \               /   \
 * 1     null         null    2
 * /   \                      /  \
 * null  null                 null null
 * [null,1,null,2,null]     [null, 1, null,2,null]
 */
public class TreeNodeSerial {

    /**
     * 先序遍历的方式序列化二叉树
     *
     * @param head
     * @return
     */
    public static Queue<String> preSerial(TreeNode head) {
        Queue<String> queue = new LinkedList<>();
        preSerial(head, queue);
        return queue;
    }

    public static void preSerial(TreeNode head, Queue<String> ans) {
        if (head == null) {
            ans.add(null);
            return;
        }

        ans.add(String.valueOf(head.val));
        preSerial(head.left, ans);
        preSerial(head.right, ans);
    }

    /**
     * 先序遍历反序列化
     *
     * @param queue
     * @return
     */
    public static TreeNode buildByPreQueue(Queue<String> queue) {
        if (queue == null || queue.size() == 0) {
            return null;
        }
        return preDeSerial(queue);
    }

    public static TreeNode preDeSerial(Queue<String> queue) {
        String val = queue.poll();
        if (val == null) {
            return null;
        }
        TreeNode head = new TreeNode(Integer.parseInt(val));
        head.left = preDeSerial(queue);
        head.right = preDeSerial(queue);
        return head;
    }


    /**
     * 后序方式序列化二叉树
     *
     * @param head
     * @return
     */
    public static Queue<String> posSerial(TreeNode head) {
        Queue<String> queue = new LinkedList<>();
        posSerial(head, queue);
        return queue;
    }

    public static void posSerial(TreeNode head, Queue<String> queue) {
        if (head == null) {
            queue.add(null);
            return;
        }
        posSerial(head.left, queue);
        posSerial(head.right, queue);
        queue.add(String.valueOf(head.val));
    }

    public static TreeNode buildByPosQueue(Queue<String> queue) {
        if (queue == null || queue.size() == 0) {
            return null;
        }
        Stack<String> stack = new Stack<>();
        while (!queue.isEmpty()) {
            stack.add(queue.poll());
        }
        return posb(stack);
    }

    public static TreeNode posb(Stack<String> stack) {
        String val = stack.pop();
        if (val == null) {
            return null;
        }
        TreeNode head = new TreeNode(Integer.parseInt(val));
        head.left = posb(stack);
        head.right = posb(stack);
        return head;
    }


    /**
     * 按层遍历，序列化
     *
     * @param x
     * @return
     */
    public static Queue<String> levelSerial(TreeNode x) {
        if (x == null) {
            return null;
        }
        Queue<String> result = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(x);
        result.add(String.valueOf(x.val));
        while (!queue.isEmpty()) {
            x = queue.poll();
            if (x.left != null) {
                result.add(String.valueOf(x.left.val));
                queue.add(x.left);
            } else {
                result.add(null);
            }

            if (x.right != null) {
                result.add(String.valueOf(x.right.val));
                queue.add(x.right);
            } else {
                result.add(null);
            }
        }
        return result;
    }

    /**
     * 按层方式反序列号
     *
     * @param levelList : 序列化后的结果集
     * @return
     */
    public static TreeNode levelDeSerial(Queue<String> levelList) {
        if (levelList == null || levelList.size() == 0) {
            return null;
        }

        TreeNode head = generateNode(levelList.poll());
        Queue<TreeNode> queue = new LinkedList<>();
        if (head != null) {
            queue.add(head);
        }
        TreeNode node;
        while (!levelList.isEmpty()) {
            node = queue.poll();
            node.left = generateNode(levelList.poll());
            if (node.left != null) {
                queue.add(node.left);
            }

            node.right = generateNode(levelList.poll());
            if (node.right != null) {
                queue.add(node.right);
            }
        }

        return head;
    }

    public static TreeNode generateNode(String val) {
        if (val == null) {
            return null;
        }
        return new TreeNode(Integer.parseInt(val));
    }

    public static void main(String[] args) {
        int testTimes = 100_0000;
        for (int i = 0; i < testTimes; i++) {
            TreeNode head = BinaryTreeCreator.buildTreeNode(10, 100);
            Queue<String> ans1 = preSerial(head);
            Queue<String> ans2 = posSerial(head);
            Queue<String> ans3 = levelSerial(head);

            TreeNode h1 = buildByPreQueue(ans1);
            TreeNode h2 = buildByPosQueue(ans2);
            TreeNode h3 = levelDeSerial(ans3);

            if (!CheckSameTree.isSameTree(h1, h2) && !CheckSameTree.isSameTree(h1, h3)) {
                System.out.println("Oops");
                break;
            }
        }
    }

}
